#include"Prime_number.h"




const int Max_Size = 1e8+7;
int prime[Max_Size];//存质数
bool pri[Max_Size];//true为合数，false为质数
int Prime1(int n)//正常求质数的方法
{
	int cnt = 0;// 保存质数的个数，初始化为0  

	// 遍历从2到n的所有整数，检查它们是否是质数  
	for (int i = 2; i < n; ++i)
	{
		bool flag = false;// 标记变量，用于表示i是否不是质数。初始化为false，即假设i是质数  
		for (int j = 2; j < i; ++j)
		{
			// 如果i能被j整除（除了i本身），则i不是质数  
			if (i % j == 0)
			{
				flag = true;
				// 当找到一个因子时，可以立即跳出循环，因为已经确定i不是质数了  
				break;
			}
		}

		// 如果flag仍为false，则i是质数，增加质数计数器  
		if (!flag)
			cnt++;
	}

	// 返回小于或等于n的质数的数量  
	return cnt;
}

int Prime2(int n)//优化
{
	int cnt = 0;// 保存质数的个数，初始化为0  

	// 遍历从2到n的所有整数，检查它们是否是质数  
	for (int i = 2; i < n; ++i)
	{
		bool flag = false;// 标记变量，用于表示i是否不是质数。初始化为false，即假设i是质数  
		for (int j = 2; j*j <= i; ++j)
		{
			// 如果i能被j整除（除了i本身），则i不是质数  
			if (i % j == 0)
			{
				flag = true;
				// 当找到一个因子时，可以立即跳出循环，因为已经确定i不是质数了  
				break;
			}
		}

		// 如果flag仍为false，则i是质数，增加质数计数器  
		if (!flag)
			cnt++;
	}

	// 返回小于或等于n的质数的数量  
	return cnt;
}

// 埃拉托斯特尼筛法，用于找出小于n的所有素数，并返回素数的数量  
// 注意：通常该算法的时间复杂度为O(N log log N)，而不是N*logN*logN  
int Ehrlich_sieve(int n)
{
	int cnt = 0; // 计数器，用于记录素数的数量  
	// 假设pri数组已经定义并初始化为0（false），表示该数可能是素数  
	// bool pri[n] = {0}; // 这里通常需要在函数外部定义和初始化  

	// 假设prime数组已经定义，用于存储找到的素数  
	// int prime[适当大小]; // 需要在函数外部定义足够大的数组来存储素数  

	// 从2开始遍历到n-1，检查每个数是否是素数  
	for (int i = 2; i < n; ++i)
	{
		// 如果pri[i]为false（即i未被标记为非素数），则i是素数  
		if (!pri[i])
		{
			// 将素数i添加到prime数组中  
			prime[cnt++] = i;

			// 标记i的所有倍数（除了i本身）为非素数  
			// 从i的平方开始标记，因为小于i平方的数要么已经被标记过，要么是素数  
			for (long long j = 1LL * i * i; j < n; j += i)
			{
				pri[j]++; // 标记j为非素数  
			}
		}
	}

	// 返回找到的素数数量  
	return cnt;
}

// 欧拉筛（Euler Sieve），也称为线性筛，用于筛选小于n的所有素数  
// 复杂度为O(N)，每个合数只被它的最小质因数筛掉一次  
int Euler_sieve(int n) {
	int cnt = 0;  // 用于记录找到的素数数量  
	// pri[] 数组未在函数中定义，但通常是一个布尔数组，用于标记每个数是否为素数（false表示是素数）  
	// prime[] 数组用于存储找到的素数  

	// 从2开始遍历到n-1（注意：因为n本身不是待筛选的数，所以到n-1即可）  
	for (int i = 2; i < n; ++i) {
		// 如果当前数i未被标记为合数（即i是素数）  
		if (!pri[i]) {
			// 将i添加到prime数组中，并增加素数数量  
			prime[cnt++] = i;
		}

		// 对于当前找到的每一个素数prime[j]，用它去筛掉合数  
		for (int j = 0; j < cnt && 1LL * prime[j] * i < n; ++j) {
			// k是prime[j]和i的乘积，即一个待检查的数  
			int k = prime[j] * i;
			// 将k标记为合数  
			pri[k]++;

			// 如果i能被prime[j]整除（即i含有prime[j]这个质因子）  
			// 那么prime[j] * i的后续倍数（如prime[j+1]*i）一定已经被之前的prime[j]*i筛过了  
			// 所以可以跳出内层循环，继续检查下一个i  
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
	// 返回找到的素数数量  
	return cnt;
}

// Test函数用于测试线性筛（Euler_sieve）和埃式筛法（Ehrlich_sieve）的时间效率  
void Test()
{
	int N = 0; // 定义一个整数N，用于存储用户输入的数据量  

	// 使用while循环，不断读取用户输入的N值，直到输入结束（例如输入非整数）  
	while (cin >> N)
	{
		cout << "数据量为" << N << ": " << endl; // 输出当前测试的数据量N  

		// 记录开始时间  
		clock_t time1 = clock();

		// 调用埃式筛法函数，计算小于等于N的质数个数，并返回该个数  
		int cnt1 = Ehrlich_sieve(N);

		// 记录结束时间  
		clock_t time2 = clock();

		// 输出埃式筛法找到的质数个数和所消耗的时间  
		cout << "质数的个数：" << cnt1 << endl;
		cout << "Ehrlich_sieve：" << (time2 - time1) * 1000.0 / CLOCKS_PER_SEC << "ms" << endl; // 注意：转换为毫秒  

		// 清空prime和pri数组，为下一次测试做准备  
		// 假设prime是存储质数的数组，Max_Size是数组的最大大小  
		// 假设pri是标记是否为质数的布尔数组  
		memset(prime, 0, sizeof(int) * Max_Size);
		memset(pri, 0, sizeof(bool) * Max_Size);

		// 记录开始时间  
		clock_t time3 = clock();

		// 调用线性筛法函数，计算小于等于N的质数个数，并返回该个数  
		int cnt2 = Euler_sieve(N);

		// 记录结束时间  
		clock_t time4 = clock();

		// 输出线性筛法找到的质数个数和所消耗的时间  
		cout << "质数的个数：" << cnt2 << endl;
		cout << "Euler_sieve：" << (time4 - time3) * 1000.0 / CLOCKS_PER_SEC << "ms" << endl; // 注意：转换为毫秒  

		// 再次清空prime和pri数组
		memset(prime, 0, sizeof(int) * Max_Size);
		memset(pri, 0, sizeof(bool) * Max_Size);
	}
}